/*
给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。

示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list
 */

package LC0019;

public class Solution1 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int len = 0;
        ListNode h = head;
        while (h != null) {
            h = h.next;
            len++;
        }
        //长度等于 1 ，再删除一个结点就为 null 了
        if (len == 1) {
            return null;
        }

        int rm_node_index = len - n;

        //如果删除的是头结点
        if (rm_node_index == 0) {
            return head.next;
        }

        //找到被删除结点的前一个结点
        h = head;
        for (int i = 0; i < rm_node_index - 1; i++) {
            h = h.next;
        }

        //改变指向
        h.next = h.next.next;
        return head;
    }

}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
